namespace LeetCode1808MASD {

    function minAbsoluteSumDiff(nums1: number[], nums2: number[]): number {
        if (!nums1 || !nums2 || nums1.length == 0 || nums1.length != nums2.length)
            return 0;
        // 题设MOD(两个数组内的单个元素不会超过MOD)
        const MOD = 1000000007;
        const size = nums1.length;
        // 绝对值总和
        let all: number = 0;
        // 差异最大值的序号
        let maxI: number = 0;
        let maxDel: number = 0;
        for (let i = 0; i < size; i++) {
            const del = Math.abs(nums1[i] - nums2[i]) % MOD;
            all = (all + del) % MOD;
            if (del > maxDel) {
                maxI = i;
                maxDel = del;
            }
        }
        // 特殊处理
        if (size == 1)
            return all;
        // 最大差值时n2序号对应的值
        const n2Target = nums2[maxI];
        // 升序排列n1
        nums1.sort((a, b) => a - b);
        // 查找一个最接近n2Target的值
        if (n2Target <= nums1[0]) {
            return (all - maxDel) + (Math.abs(nums1[0] - n2Target) % MOD);
        }
        else if (n2Target >= nums1[size - 1]) {
            return (all - maxDel) + (Math.abs(nums1[size - 1] - n2Target) % MOD);
        }
        else {
            // n2Target 介于n1数组的最大最小区间内，需要查找合适值
            let l0 = 0, l1 = size - 1;
            let tempDel = -1;
            while (l0 < l1) {
                const mid = Math.floor((l1 - l0) / 2) + l0;
                const temp = nums1[mid];
                const del = Math.abs(temp - n2Target) % MOD;
                if (del == 0) {
                    return (all - maxDel) + del;
                }
                else if (temp < n2Target) {
                    l0 = mid + 1;
                    if (tempDel >= 0 && tempDel > del)
                        tempDel = del;
                } else {
                    l1 = mid - 1;
                    if (tempDel >= 0 && tempDel > del)
                        tempDel = del;
                }
            }
            // TODO HarryNR 未验证
            return (all - maxDel) + tempDel;
        }
    };

}